package algorithm.dp;

public class 等差数列划分 {
    /*
     * 如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。
     * 
     * 例如，以下数列为等差数列:
     * 
     * 1, 3, 5, 7, 9 7, 7, 7, 7 3, -1, -5, -9 以下数列不是等差数列。
     * 
     * 1, 1, 2, 5, 7
     * 
     * 
     * 数组 A 包含 N 个数，且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。
     * 
     * 如果满足以下条件，则称子数组(P, Q)为等差数组：
     * 
     * 元素 A[P], A[p + 1], ..., A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。
     * 
     * 函数要返回数组 A 中所有为等差数组的子数组个数。
     * 
     * 
     * 
     * 示例:
     * 
     * A = [1, 2, 3, 4]
     * 
     * 返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。
     */
    public int numberOfArithmeticSlices(int[] A) {
        /*
         * 如果2等差数组有交集即a[i][j] b[m][n] j>m，那么这2个等差数组一定能够合并c[i][n]，所以等价于 找到不同的等差数组
         */
        int len = A.length;
        int[] maxLen = new int[len + 5];// 第i个数和前n个数凑成等差数列，形成的最大长度
        maxLen[0] = 1;
        maxLen[1] = 2;
        int[] count = new int[len + 5];
        count[3] = 1;
        for (int i = 4; i <= len; i++) {
            count[i] = count[i - 1] + i - 2;
        }
        int sum = 0;
        for (int i = 2; i < len; i++) {
            if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
                // 能夠和前面形成等差
                maxLen[i] = maxLen[i - 1] + 1;
            } else {
                // 不能和前面形成等差，結算
                sum += count[maxLen[i - 1]];
                maxLen[i] = 2;
            }
        }
        if (len > 0 && maxLen[len - 1] >= 3) {
            // 再结算一次
            sum += count[maxLen[len - 1]];
        }
        return sum;
    }

    public static void main(String[] args) {
        等差数列划分 run = new 等差数列划分();
        int[] a = { 1, 2, 3, 4 };
        System.out.println(run.numberOfArithmeticSlices(a));
    }
}
